<!DOCTYPE html>
<html>
  <head>
    <title>Numεrωmikωn</title>
    <link rel="stylesheet" href="../stock.css">
    <link rel="icon" type="image/x-icon" href="../favicon.ico">
    <meta content="text/html;charset=utf-8" http-equiv="Content-Type"/>
    <meta name="viewport" content="width=device-width, initial-scale=1" />
  </head>

  <body>
    <div class ="nav">
      <a href="../index">Indεχ</a>
      <a href="../clanky">Článκy</a>
      <a class="active" href="../googologie">Gωωgωlωgiε</a>
      <a href="../o_mne">Ω mně</a>
    </div>

    <div class="content-googology">
      <h1>Goodsteinova věta ~ <i>f<sub>ε<sub>0</sub></sub>(n)</i></h1>

      <p>Jsme připraveni probrat Goodsteinovu větu. Nebude to snadné, ale zdoláme-li ji, odemkneme si dveře do
      nové oblasti googologie. Budeme se spoléhat na naši zběhlost ve Wainerově posloupnosti ordinálů, tudíž pokud ti
      něco není jasné, doporučuji znovu si přečíst předchozí části.</p>

      <p>Goodsteinovy posloupnosti závisí na pojmu "hereditary base-<i>n</i> notation". Nepodařilo se mi vyhledat překlad, 
      proto použiji vlastní: dědičný zápis o základu <i>n</i>.</p>

      <p>V dědičném zápisu o základu <i>n</i>, kde <i>n</i> je přirozené číslo větší než <i>1</i>, libovolné číslo <i>m</i> je
      zapsáno jako součet násobků mocnin <i>n</i>:</p>

      <div class="math"> 
        <p>m = a<sub>k</sub>n<sup>k</sup> + a<sub>k - 1</sub>n<sup>k - 1</sup> + ... + a<sub>0</sub></p>
      </div>

      <p>Kde každý součinitel <i>a</i> splňuje: <i>0 ≤ a &lt n</i>, též <i>a<sub>k</sub> ≠ 0</i>.</p>

      <p>------</p>

      <p>Zkusme přepsat <i>35</i> na dvojkový základ:</p>

      <div class="math"> 
        <p>35 = 32 + 2 + 1 = 2<sup>5</sup> + 2<sup>1</sup> + 2<sup>0</sup></p>
      </div>

      <p>Tedy <i>35</i> bychom napsali jako <i>100011</i>. Vyzkoušíme převést <i>100</i> na trojkový základ:</p>

      <div class="math"> 
        <p>100 = 81 + 18 + 1 = 3<sup>4</sup> + 2 * 3<sup>2</sup> + 3<sup>0</sup></p>
      </div>

      <p>Tedy <i>10201</i>.</p>

      <p>------</p>

      <p>Všimni si, že mocnitele jsme nepřepsali do <i>n</i> základu. Kdybychom tak učinili, stvoříme právě dědičný zápis o základu <i>n</i>. 
      Patrně se může stát, že ani po druhém opakování je nepřepíšeme do <i>n</i> základu; musíme pak tento postup opakovat víckrát.</p>

      <p>Přepišme tedy <i>35</i> a <i>100</i> na dědičné zápisy o základech <i>2</i> a <i>3</i>:</p>

      <div class="math"> 
        <p>35 = 2<sup>2<sup>2<sup>1</sup></sup>+ 1</sup> + 2<sup>1</sup> + 1</p>
        <p>100 = 3<sup>3<sup>1</sup>+ 1</sup> + 2 * 3<sup>2</sup> + 1</p>
      </div>

      <p>------</p>

      <p>Teď si povíme, co je Goodsteinova posloupnost. Popíšeme ji slovně:</p>

      <p>První prvek posloupnosti je <i>G<sub>0</sub>(n).</i></p>

      <p>Pro <i>G<sub>0</sub>(n)</i> přepíšeme <i>n</i> do dědičného zápisu o dvojkovém základu.</p>

      <p>Pro <i>G<sub>k</sub>(n)</i> vezmeme zápis <i>G<sub>k - 1</sub>(n)</i>, zvětšíme všechny číslice <i>a</i>, které jsou rovny základu, o <i>1</i> a
      z výsledného zápisu odečteme <i>1</i>. Následně zvětšíme základ o <i>1</i>.</p>

      <p>Pokračujeme, dokud <i>G<sub>k</sub>(n)</i> není rovno nule.</p>

      <p>Index <i>k</i>, pro které je <i>G<sub>k</sub>(n)</i> rovno nule, je výsledek pro <i>G(n)</i></p>

      <p>------</p>

      <p>A jak to bude vypadat? Podívejme se:</p>

      <div class="math"> 
        <p>G<sub>0</sub>(0) = 0</p>
      </div>

      <p>To dá rozum; ani naše rychle rostoucí hierarchie by s nulou tolik nedokázala! Zvětšíme vstupy:</p>

      <div class="math">
        <p>G<sub>0</sub>(1) = 1</p>
        <p>G<sub>1</sub>(1) = 1 - 1 = 0</p>
      </div>

      <p>Samozřejmě! Zkusíme ještě dvojku a trojku:</p>

      <div class="math"> 
        <p>G<sub>0</sub>(2) = 2<sup>1</sup></p>
        <p>G<sub>1</sub>(2) = 3<sup>1</sup> - 1 = 2</p>
        <p>G<sub>2</sub>(2) = 2 - 1 = 1</p>
        <p>G<sub>3</sub>(2) = 1 - 1 = 0</p>
      </div>

      <p>Takže <i>G(2)</i> je rovno třem. Nudné, ale očekávané. Jdeme dál:</p>

      <div class="math"> 
        <p>G<sub>0</sub>(3) = 2<sup>1</sup> + 1</p>
        <p>G<sub>1</sub>(3) = 3<sup>1</sup></p>
        <p>G<sub>2</sub>(3) = 4<sup>1</sup> - 1 = 3</p>
        <p>G<sub>3</sub>(3) = 3 - 1 = 2</p>
        <p>G<sub>4</sub>(3) = 2 - 1 = 1</p>
        <p>G<sub>5</sub>(3) = 1 - 1 = 0</p>
      </div>

      <p>Proč opět tolik povyku kvůli něčemu tak pomalu rostoucímu? No dobře, poslední šance:</p>

      <div class="math"> 
        <p>G<sub>0</sub>(4) = 2<sup>2</sup></p>
        <p>G<sub>1</sub>(4) = 3<sup>3</sup> - 1 = 2 * 3<sup>2</sup> + 2 * 3 + 2</p>
        <p>G<sub>2</sub>(4) = 2 * 4<sup>2</sup> + 2 * 4 + 1</p>
        <p>G<sub>3</sub>(4) = 2 * 5<sup>2</sup> + 2 * 5</p>
        <p>G<sub>4</sub>(4) = 2 * 6<sup>2</sup> + 2 * 6 - 1 = 2 * 6<sup>2</sup> + 6 + 5</p>
        <p>G<sub>5</sub>(4) = 2 * 7<sup>2</sup> + 7 + 4</p>
        <p>...</p>
        <p>G<sub>9</sub>(4) = 2 * 11<sup>2</sup> + 11</p>
        <p>G<sub>10</sub>(4) = 2 * 12<sup>2</sup> + 11</p>
        <p>...</p>
        <p>G<sub>22</sub>(4) = 2 * 24<sup>2</sup> - 1 = 24<sup>2</sup> + 23 * 24 + 23</p>
        <p>...</p>
        <p>G<sub>3 * 2<sup>402653209</sup> - 3</sub>(4) = 2 * (3 * 2<sup>402653209</sup> - 3)</p>
        <p>...</p>
        <p>G<sub>3 * 2<sup>402653211</sup> - 3</sub>(4) = 0</p>
      </div>

      <p>------</p>

      <p>Zničehonic to vyskočilo na poměrně velké číslo! Ale opravdu to roste rychleji než všechno, co jsme si zatím ukázali? Vizme výsledky
      větších vstupních hodnot:</p>

      <div class="math"> 
        <p>G(12) = f<sub>ω + 1</sub>(f<sub>3</sub>(3)) - 3</p>
      </div>

      <p>Vždyť to je mnohem větší než Grahamovo číslo! A jak vypadají další?</p>

      <div class="math"> 
        <p>G(64) = f<sub>ω<sup>ω</sup> + 3</sub>(3) - 3</p>
      </div>

      <p>------</p>

      <p>To je šílené! Jednoduchá pravidla, malé vstupní hodnoty, a přesto to převálcovalo vše, co jsme si již ukázali! Ale jak je to možné?
      Chicon v 1983 dokázal tento vztah:</p>

      <div class="math"> 
        <p>G(n) = h<sub>R<span class="supsub"><sup>ω</sup><sub>2</sub></span>(n + 1)</sub>(1) - 1</p>
      </div>

      <p>Kde <i>R<span class="supsub"><sup>ω</sup><sub>2</sub></span>(n + 1)</sub></i> je výsledek, přepsali-li bychom <i>n</i> do dědičného zápisu o dvojkovém základu a
    všechny dvojky zaměnili za <i>ω</i>. Například:</p>

      <div class="math"> 
        <p>G(12) = h<sub>ω<sup>ω + 1</sup> + ω<sup>ω</sup> + 1</sub>(1) - 1</p>
      </div>

      <p>------</p>

      <p>Neukazovali jsme si, jak převádět mezi Hardyho hierarchií a rychle rostoucí hierarchií v těchto složitějších případech, naštěstí Caicedo v 2007
      to pořešil za nás. V případě, že <i>n = 2<sup>m<sub>1</sub></sup> + 2<sup>m<sub>2</sub></sup> + ... + 2<sup>m<sub>k</sub></sup></i>, kde
      <i>m<sub>1</sub> &gt m<sub>2</sub> &gt ... &gt m<sub>k</sub></i>:</p>

      <div class="math"> 
        <p>G(n) = f<sub>R<span class="supsub"><sup>ω</sup><sub>2</sub></span>(m<sub>1</sub>)</sub>(f<sub>R<span class="supsub"><sup>ω</sup><sub>2</sub></span>(m<sub>2</sub>)</sub>(...(f<sub>R<span class="supsub"><sup>ω</sup><sub>2</sub></span>(m<sub>k</sub>)</sub>(3))...)</p>
      </div>

      <p>------</p>

      <p>Tím jsme si před chvílí odvodili, že <i>G(12)</i> je výrazně větší než Grahamovo číslo. Z těchto dvou rovností plyne:</p>

      <div class="math"> 
        <p>G(2 ↑↑ n) = f<sub>ω ↑↑ (n - 1)</sub>(3) - 3</p>
      </div>

      <p>------</p>

      <p>Aby tomu mohla čelit naše rychle rostoucí hierarchie, musíme využít samotný vrchol Wainerovy posloupnosti:</p>

      <div class="math"> 
        <p>f<sub>ε<sub>0</sub></sub>(n) = f<sub>ω ↑↑ (n - 1)</sub>(n)</p>
      </div>

      <p>Už od pohledu vidíme, že to bude aspoň o krok napřed vůči Goodsteinově funkci. Konečně si povíme o Goodsteinově větě. Shrnu ji krátce, jelikož 
      celý důkaz je příliš složitý: pro libovolné <i>n</i> v <i>G(n)</i> je takové konečné <i>k</i>, aby <i>G<sub>k</sub>(n)</i> bylo rovno nule.</p>

      <p>Proč je to tak důležité? Protože Peanova aritmetika toto tvrzení nedokáže potvrdit. Abychom toto tvrzení dokázali, potřebujeme mnohem mocnější
      sadu axiomů. Obdobně bychom nemohli potvrdit konečnost žádné funkce, která by rostla rychleji než Goodsteinova.</p>

      <p>Přežili jsme střet s Goodsteinovou větou a vyprázdnili jsme Wainerovu posloupnost ordinálů. Čeká nás obrovské území nekonečných ordinálů, pro které se
      budeme muset buď naučit nové fundamentální posloupnosti, nebo si vytvořit vlastní. Určitě bychom přišli na vlastní posloupnosti, ale bude lehčí se podívat na
      výtvory ostatních.</p>
    </div>

    <footer>
      <p class="footer"><a class="silent" href="https://creativecommons.org/licenses/by/4.0/" target="_blank">Kristian Tichota (CC-BY-4.0)</a></p>
    </footer>
  </body>
</html>
